package com.leetcode.algo;

import cn.hutool.core.util.ArrayUtil;
import org.apache.commons.lang3.ArrayUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * @Author :Jaden;
 * @TIME :2021/02/26;
 * @discription:
4. 寻找两个正序数组的中位数
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

示例 3：

输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000

示例 4：

输入：nums1 = [], nums2 = [1]
输出：1.00000

示例 5：

输入：nums1 = [2], nums2 = []
输出：2.00000
 */
public class Algo4 {

    /*
        思路1：将数组逻辑合并，然后使用快排，最后输出中位数。时间复杂度是：n+m Log(N+M)。
        执行用时: 5 ms
        内存消耗: 39.8 MB
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        double median = 0.0d;
//        int[] bothArray = ArrayUtils.addAll(nums1, nums2);
        int[] bothArray = new int[nums1.length + nums2.length];
        for (int n1 = 0 ; n1 < nums1.length ; n1 ++) {
            bothArray[n1] = nums1[n1];
        }
        for (int n2 = 0 ; n2 < nums2.length ; n2 ++) {
            bothArray[nums1.length + n2] = nums2[n2];
        }
        quickSort(bothArray, 0 , bothArray.length - 1);

        for (int i : bothArray) {
            System.out.print(i + " ");
        }
        if ((nums1.length + nums2.length)%2 == 0) {
            median = (bothArray[((nums1.length + nums2.length)/2) - 1] + bothArray[((nums1.length + nums2.length)/2)] )/2.;
        }else {
            median = bothArray[((nums1.length + nums2.length)/2)];
        }
        System.out.println(median);
        return median;
    }

    public void quickSort(int[] array, int left , int right) {
        if (left > right ) {
            return;
        }
        int base = array[left];
        int i = left, j = right;
        while (i != j) {
            while (i < j && array[j] >= base) {
                j--;
            }
            while (i < j && array[i] <= base) {
                i++;
            }
            if (i < j) {
                int tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
            }
        }
        //i j 相遇了
        // 将基准数放到中间的位置（基准数归位）
        array[left] = array[i];
        array[i] = base;

        // 递归，继续向基准的左右两边执行和上面同样的操作
        // i的索引处为上面已确定好的基准值的位置，无需再处理
        quickSort(array, left, i - 1);
        quickSort(array, i + 1, right);

    }

    /*
        方法2：使用二分查找变形。
        来自：leetcode
        执行用时: 3 ms
        内存消耗: 39.9 MB
        果然快了一些

    */
    public double findMedianSortedArrays2(int[] nums1, int[] nums2) {

        double median = 0.0d;
        int length1 = nums1.length, length2 = nums2.length;
        int totalLength = length1 + length2;

        if (totalLength % 2 == 1) {
            // 总长度为奇数时
            int midIndex = totalLength / 2;
            median = getKthElement(nums1, nums2, midIndex + 1);
            return median;
        } else {
            //总长度为偶数时
            int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
            median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
            return median;
        }
    }

    public int getKthElement(int[] nums1, int[] nums2, int k) {

        //1、获取两个数组的长度
        int length1 = nums1.length, length2 = nums2.length;
        //2、创建两个指针
        int index1 = 0, index2 = 0;
        int kthElement = 0;

        while (true) {
            // 边界情况
            if (index1 == length1) {
                //到达了 nums1的边界，表示nums1的数字全都小于中位数，此时应该返回num2中 index + k - 1 在num2找中位数
                return nums2[index2 + k - 1];
            }
            if (index2 == length2) {
                //
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                //当 k = 1 时 说明已经找到中位数的位置，下一个就是中位数，所以去一个最小的即可。
                return Math.min(nums1[index1], nums2[index2]);
            }

            // 正常情况
            int half = k / 2;
            int newIndex1 = Math.min(index1 + half, length1) - 1;
            int newIndex2 = Math.min(index2 + half, length2) - 1;
            int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            } else {
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }
    }

    public static void main(String[] args) {
        Algo4 algo4 = new Algo4();
        algo4.findMedianSortedArrays(new int[] {1,2}, new int[] {3,4});
    }
}
